package algorithm.array;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * 找出一个数组中第三大的元素，如果数组数量不到3，找出最大的
 */
public class ThirdMax {

    public static void main(String[] args) {
        int [] nums = {3,2,1,5,96,3,2,5,96,96};

        System.out.println(thirdMax1(nums));
    }

    public static int thirdMax(int[] nums) {

        Arrays.sort(nums);
        reverse(nums);
        for (int i = 1, diff = 1; i < nums.length; ++i) {
            if (nums[i] != nums[i - 1] && ++diff == 3) { // 此时 nums[i] 就是第三大的数
                return nums[i];
            }
        }
        return nums[0];
    }

    public static int thirdMax1(int[] nums) {

        TreeSet<Integer> s = new TreeSet<Integer>();
        for (int num : nums) {
            s.add(num);
            if (s.size() > 3) {
                s.remove(s.first());
            }
        }
        return s.size() == 3 ? s.first() : s.last();
    }

    public static void reverse(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
